package algorithms;

import java.util.Arrays;

/**
 * 1.
 * 如果不是取mid+1,mid-1，而是都取mid 会陷入死循环
 * 有3个数字位置是 0 1 2
 * 第一次查找
 * mid = (0 + 2) / 2 = 1，比较1的位置
 * 第二次比较,如果取mid,而不是mid-1 +1的话
 * mid = (0 +1 ) / 2 = 0, 比较0的位置
 * mid = (1+2) / 2 = 1，比较1的位置，1已经比较过了，所以不对
 *
 * 2.
 * 为什么while循环的条件中是<= 而不是< ?
 * while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，
 * 或者带个具体的数字进去 [3, 2]，可见这时候搜索区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。
 * 所以这时候 while 循环终止是正确的，直接返回 -1 即可。
 *
 * while(left < right) 的终止条件是 left == right，写成区间的形式就是 [left, right]，或者带个具体的数字进去 [2, 2]，
 * 这时候搜索区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，
 * 如果这时候直接返回 -1 就是错误的。
 */
public class BinarySearch {

    private static int rank(int key, int[] array){
        // 最小索引
        int begin = 0;
        // 最大索引
        int end = array.length - 1;
        while (begin <= end) {
            // 被查找的键要么不存在，要么必然存在于a[begin...end]中
            int mid = (begin + end) / 2;
            if (key < array[mid]) {
                end = mid - 1;
            } else if (key > array[mid]) {
                begin = mid + 1;
            } else {
                return  mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 0};
        // 数组必须是有序的
        Arrays.sort(array);
        int rank = rank(2, array);
        System.out.println(rank);
    }

}
    